{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "7d47904d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "69 和 7 的最大公约数是 1, 逆元存在，为 10\n"
     ]
    }
   ],
   "source": [
    "def extended_euclidean_algorithm(a, b):\n",
    "    x1, y1, x2, y2 = 1, 0, 0, 1\n",
    "    \n",
    "    while b:\n",
    "        q = a // b\n",
    "        a, b = b, a % b\n",
    "        x1, x2 = x2, x1 - q * x2\n",
    "        y1, y2 = y2, y1 - q * y2\n",
    "\n",
    "    return a, x1, y1\n",
    "\n",
    "# 示例\n",
    "y = 7\n",
    "n = 69\n",
    "gcd_result, k, w = extended_euclidean_algorithm(n, y)\n",
    "if gcd_result == 1:\n",
    "    print(f'{n} 和 {y} 的最大公约数是 {gcd_result}, 逆元存在，为 {w}')\n",
    "else:\n",
    "    print(f'{n} 和 {y} 的最大公约数是 {gcd_result}, 逆元不存在')\n",
    "\n",
    "# 69 和 7 的最大公约数是 1, 逆元存在，为 10\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "89fe8388",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7 和 69 的最大公约数是 1, 逆元存在，为 10\n"
     ]
    }
   ],
   "source": [
    "def gcd(a, b):\n",
    "    if a < b :\n",
    "          a, b = b, a\n",
    "    while a % b != 0 :\n",
    "          a, b = b, a % b\n",
    "    return b\n",
    "\n",
    "def ext_gcd(a, b):\n",
    "    if b == 0:\n",
    "        return 1, 0\n",
    "    else:\n",
    "        x, y = ext_gcd(b, a%b)\n",
    "        x, y = y, x - (a//b) * y\n",
    "        return x, y\n",
    "\n",
    "def get_inverse(a, N):\n",
    "    if gcd(a, N) == 1:\n",
    "        x, y = ext_gcd(a, N)\n",
    "        return (x + N) % N\n",
    "    print(\"No inverse!\")\n",
    "    return 0\n",
    "\n",
    "a = 7\n",
    "N = 69\n",
    "print(f'{a} 和 {N} 的最大公约数是 {gcd(a, N)}, 逆元存在，为 {get_inverse(a, N)}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "6c55edfb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n"
     ]
    }
   ],
   "source": [
    "# 直接掉第三方包求模乘法逆元\n",
    "from Crypto.Util.number import *\n",
    "print(inverse(7, 69))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
